package com.company.algo.niuke;

import com.company.algo.pojo.ListNode;

import java.util.Stack;

//腾讯-反转链表
//使用Java栈的方式，这里的注意点是原来的头结点的next需要置为null，否则会导致遍历时无限循环，导致超时
public class ReverseLinkedList {
    public ListNode ReverseList(ListNode head) {
        if (head==null || head.next == null) return head;
        Stack<ListNode> stack = new Stack<>();
        ListNode tmp = head;
        while(tmp!=null){
            stack.push(tmp);
            tmp = tmp.next;
        }
        //关键在于这里，原来的头结点的next要置为空，否则会构成循环列表，因为原head是新链表的为尾节点
        //而stack.pop该节点后会退出while循环，导致原head节点的next是不被覆盖的
        head.next = null;
        ListNode node = stack.pop();
        ListNode newHead = node;
        while(!stack.isEmpty()){
            node.next = stack.pop();
            node = node.next;
        }
        return newHead;
    }

    public static void main(String[] args) {
        ReverseLinkedList Main = new ReverseLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode newHead = Main.ReverseList(head);
        while (newHead!=null){
            System.out.print(newHead.val+" ");
            newHead = newHead.next;
        }

    }
}
